package com.cat.graphTheory;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/shortest-path-with-alternating-colors/description/
 * @create 2025/9/19 19:50
 * @since JDK17
 */

public class Solution15 {
    void build(List<Integer>[] g, int[][]edges) {
        int m = edges.length;
        for (int i = 0; i < m; i++) {
            int from = edges[i][0], to = edges[i][1];
            g[from].add(to);
        }
    }
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        int[] ans = new int[n];
        List<Integer>[] gr = new List[n], gb = new List[n];
        Arrays.setAll(gr, i -> new ArrayList<>());
        Arrays.setAll(gb, i -> new ArrayList<>());
        // 建图
        build(gr, redEdges);
        build(gb, blueEdges);
        int[][] vis = new int[n][2];
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            Arrays.fill(vis[i], Integer.MAX_VALUE);
        }
        q.offer(new int[]{0, 1});   // 0 : 红 1 : 蓝
        q.offer(new int[]{0, 0});
        vis[0][0] = vis[0][1] = 0;
        while (!q.isEmpty()) {
            var x = q.poll();
            if (x[1] == 0) { // 蓝
                for (int y : gb[x[0]]) {
                    if (vis[y][1] == Integer.MAX_VALUE) {
                        vis[y][1] = vis[x[0]][0] + 1;
                        q.offer(new int[]{y, 1});
                    }
                }
            } else {    // 红
                for (int y : gr[x[0]]) {
                    if (vis[y][0] == Integer.MAX_VALUE) {
                        vis[y][0] = vis[x[0]][1] + 1;
                        q.offer(new int[]{y, 0});
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            ans[i] = Math.min(vis[i][0], vis[i][1]);
            ans[i] = ans[i] == Integer.MAX_VALUE ? -1 : ans[i];
        }
        return ans;
    }
}
